/*
 * Компоненты сильной связности
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*
 * How do you like this?
 */
#ifdef D
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	for (;0;)
#endif

enum vertex_st {
	VERTEX_ST_UNKNOWN = 0,
	VERTEX_ST_OPEN,
	VERTEX_ST_VISITED
};

/* {{{ autoarray */
struct vector {
	int *data;
	int n;
	int max;
};

void
vector_init(struct vector *v, int p)
{
	if (p < 0)
		p = 0;
	v->max = 1 << p;
	v->n = 0;
	v->data = (int *) calloc((size_t) v->max, sizeof *v->data);
}

int
vector_append(struct vector *v, int a)
{
	int *t;

	if (v->max == 0)
		vector_init(v, 0);

	if (v->n + 1 > v->max) {
		t = (int *) realloc(v->data, sizeof *t * (v->max *= 2));
		if (!t) {
			fprintf(stderr, "vector_append(): failed to allocate %d bytes\n", v->max);
			return 1;
		} else {
			v->data = t;
		}
	}

	v->data[v->n++] = a;

	return 0;
}

int
vector_sort(struct vector *v, int (*cmpf)(const void *, const void *))
{
	if (v->max > 0 && v->n > 1) {
		qsort(v->data, (size_t) v->n, sizeof *v->data, cmpf);
		return 0;
	} else {
		return 1;
	}
}

int
vector_cleanup(struct vector *v)
{
	if (v->max > 0) {
		v->max = v->n = 0;
		free(v->data);
		v->data = NULL;
		return 0;
	} else {
		return 1;
	}
}
/* }}} */

/* {{{ doubly-linked list */
struct dll_node {
	int key;
	struct dll_node *prev, *next;
};

/* {{{ functions */
/*
 * This function inserts one node pointed to by 'ins' _after_ 'node'.
 * And it doesn't give a rat's ass about anything else.
 */
struct dll_node *
dll_insert(struct dll_node *node, struct dll_node *ins)
{
	assert(node != NULL);
	if (ins == NULL) {
		fprintf(stderr, "dll_insert(): ins is NULL, not doing anything\n");
		return node;
	}

	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = ins;
	}
	ins->next = node->next;
	ins->prev = node;
	node->next = ins;
	return ins;
}

/*
 * This function extracts 'node' from a doubly-linked list and returns pointer
 * to that node, which pointers '->prev' and '->next' are not reset.
 *
 * If you really want to get rid of a node, call
 * 	free(dll_delete(unneeded_node));
 */
struct dll_node *
dll_delete(struct dll_node *node)
{
	if (!node) {
		fprintf(stderr, "dll_delete(): received NULL ptr, wtf am i supposed to delete?\n");
		return NULL;
	}
	if (node->prev) {
		assert(node->prev->next == node);
		node->prev->next = node->next;
	}
	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = node->prev;
	}
	return node;
}
/* }}} */
/* }}} */

/* {{{ adjlist w/ doubly-linked list */
struct adjlist_dll {
	struct dll_node *head;
	struct dll_node *tail;
	int _list_len;

	enum vertex_st state[2];
	int color;
	int distance;
	int prev;
};
/* {{{ functions */
void
adjl_dll_connect(struct adjlist_dll *node, int conid)
{
	struct dll_node *wanderer;

	wanderer = (struct dll_node *) malloc(sizeof *wanderer);
	wanderer->key = conid;
	wanderer->prev = wanderer->next = NULL;

	if (node->head == NULL) {
		assert(node->tail == NULL);
		node->head = node->tail = wanderer;
		node->_list_len = 1;
	} else {
		dll_insert(node->tail, wanderer);
		node->_list_len++;
	}
}

void
adjl_dll_cleanup(struct adjlist_dll *al)
{
	struct dll_node *nx = al->head, *pr = al->head;

	while (nx) {
		pr = nx;
		nx = nx->next;
		free(pr);
	}
	al->_list_len = 0;
}
/* }}} */
/* }}} */

void
dfs_walk_build_path(struct adjlist_dll *al, const int idx, struct vector *path)
{
	struct dll_node *nd = al[idx].head;

	if (al[idx].state[0] != VERTEX_ST_UNKNOWN)
		return;

	al[idx].state[0] = VERTEX_ST_OPEN;
	debug_fprintf((stderr, "inside node %d\n", idx + 1));
	while (nd) {
		if (al[nd->key].state[0] == VERTEX_ST_UNKNOWN)
			dfs_walk_build_path(al, nd->key, path);
		nd = nd->next;
	}
	debug_fprintf((stderr, "leaving node %d (adding to %d to *path)\n",
				idx + 1, idx));
	vector_append(path, idx);
	al[idx].state[0] = VERTEX_ST_VISITED;
}

void
dfs_mark_connection_space(struct adjlist_dll *al, const int idx, const int id)
{
	struct dll_node *nd = al[idx].head;

	if (al[idx].state[1] != VERTEX_ST_UNKNOWN)
		return;

	al[idx].color = id;
	al[idx].state[1] = VERTEX_ST_OPEN;
	debug_fprintf((stderr, "painting node %2d with color %02d\n",
				idx + 1, id));
	while (nd) {
		if (al[nd->key].state[1] == VERTEX_ST_UNKNOWN)
			dfs_mark_connection_space(al, nd->key, id);
		nd = nd->next;
	}
	debug_fprintf((stderr, "leaving node %2d\n", idx + 1));
	al[idx].state[1] = VERTEX_ST_VISITED;
}

int
walk_path_rev(struct vector *path, struct adjlist_dll *al)
{
	int i = path->n - 1, cs_id = 1;

	while (i >= 0) {
		if (al[path->data[i]].state[1] == VERTEX_ST_UNKNOWN)
			dfs_mark_connection_space(al, path->data[i], cs_id++);
		i--;
	}

	return cs_id - 1;
}

/* unused
int
dfs_toposort(struct adjlist_dll *al, const int idx, struct vector *path)
{
	struct dll_node *nd = al[idx].head;
	al[idx].state = VERTEX_ST_OPEN;
	while (nd) {
		if (al[nd->key].state == VERTEX_ST_OPEN)
			return 1;
		if (al[nd->key].state == VERTEX_ST_UNKNOWN &&
				dfs_toposort(al, nd->key, path) == 1)
			return 1;
		nd = nd->next;
	}
	vector_append(path, idx);
	al[idx].state = VERTEX_ST_VISITED;
	return 0;
}
*/

int
main(int argc, char **argv)
{
	struct adjlist_dll *al;
	struct adjlist_dll *al_tr;
	static struct vector lst;
	int i, n, m, a, b;
	int str_conn_comp_n;

	scanf("%d%d", &n, &m);
	vector_init(&lst, 6);
	al = (adjlist_dll *) calloc(n, sizeof *al);
	al_tr = (adjlist_dll *) calloc(n, sizeof *al_tr);
	for (i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		--a, --b;
		adjl_dll_connect(al + a, b);
		adjl_dll_connect(al_tr + b, a);
	}

	for (i = 0; i < n; i++) {
		al[i].state[0] = al[i].state[1] = VERTEX_ST_UNKNOWN;
		al_tr[i].state[0] = al_tr[i].state[1] = VERTEX_ST_UNKNOWN;
	}

	for (i = 0; i < n; i++)
		dfs_walk_build_path(al, i, &lst);
	str_conn_comp_n = walk_path_rev(&lst, al_tr);
	printf("%d\n", str_conn_comp_n);

	for (i = 0; i < n; i++)
		printf("%d ", al_tr[i].color);
	fputc('\n', stdout);

bail:
	for (i = 0; i < n; i++) {
		adjl_dll_cleanup(al + i);
		adjl_dll_cleanup(al_tr + i);
	}
	free(al);
	free(al_tr);
	vector_cleanup(&lst);
	return 0;
}
